\documentclass[a4paper,titlepage]{article}

\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{indentfirst}
\usepackage{graphicx}

\title{Simulação do vetor-distância}
\author{Alex Rodrigo de Oliveira - 06/30403 \and
	Danilo Gaby Andersen Trindade - 06/82039}

\begin{document}

\maketitle

\section{Algoritmo vetor-distância}

O algoritmo vetor-distância é usado por alguns protocolos de rede, como o RIP, para encontrar o melhor caminho entre os nós da rede. Nele, cada roteador, que representa um nó da rede, contém uma tabela dizendo qual o melhor caminho para chegar em todos os outros nós da rede. O algoritmo baseia-se em trocas de tabelas entre esse comutadores, até que todos tenham a informação do melhor caminho para todos os outros. Neste trabalho, simulamos o funcionamento do distance vector, baseados na especificação e na implementação do protocolo RIP.

Cada roteador possui uma tabela dizendo qual o custo para chegar em cada um dos outros nós da rede e por qual vizinho ele deve enviar a informação para que ela chegue no destino pelo caminho de menor custo. Quando um roteador descobre um novo nó, um caminho melhor ou uma mudança na rede que implique em mudança na sua tabela de menor custo ele envia sua tabela atualizada para todos os seus vizinhos. Cada roteador tem um buffer para receber as tabelas dos vizinhos. Quando chega uma tabela no buffer, o roteador analisa se as novas informações que estão lá implicam em uma mudança na sua tabela de menor custo. Se a tabela de menor custo desse último roteador for atualizada, ele a envia para todos os seus vizinhos e o processo se repete até que todos da rede que serão afetados tenham recebido a nova informação.

\section{Protocolo RIP}

O protocolo RIP usa o algoritmo vetor-distância para encontrar o menor caminho entre dois pontos da rede. Ele faz uma espécie de troca de tabelas por turno, isso para evitar o excesso de tráfego na rede que a troca de tabelas pode gerar. Além disso, ele usa duas técnicas para evitar a contagem ao infinito que são a divisão do horizonte e a reversão envenenada.

A troca de tabelas por turnos é uma forma de impedir o cenário a seguir. Imagine a seguinte situação: A está conectado com B e C, mas B está mais próximo. B e C enviam tabelas com atualizações ao mesmo tempo para A, como B está mais perto, a tabela dele chega primeiro. Nesse momento, A processa o buffer, atualiza sua tabela e a envia para todos os seus vizinhos. Logo 1ms depois chega a tabela que C enviou para A. A processa o buffer novamente, atualiza sua tabela e envia para todos os vizinhos. Esse comportamento pode inundar a rede só com trocas de tabelas. Para evitar isso, o RIP envia tabelas só a cada 30s. Dessa forma, por mais distante que um roteador esteje, as tabelas de todos os vizinhos serão processadas de uma vez, como se tivessem chegado ao mesmo tempo. Por isso que nos referimos ao RIP trocar tabelas por turnos e é essa mesma idéia que usaremos nessa simulação.

O RIP calcula o melhor caminho entre dois nós da rede baseado na quantidade de saltos de um para o outro, ou seja, por quantos outros nós a informação deve passar para chegar até o destino. Dessa forma o peso de uma aresta da rede é sempre 1. Em nossa simulação, estamos usando como peso da aresta a distância entre os nós, pois isso permite visualizar melhor o funcionamento do algoritmo.

\section{Simulação}

Em nossa simulação, usamos um grafo para representar uma rede, os nós do grafo são os roteadores, as arestas são os links entre eles, e o peso da aresta é a distância quadrada entre os nós. A topologia da rede é gerada aleatoriamente da seguinte forma: O programa recebe como parâmetros a altura e largura de um mapa, um raio de vizinhança para os nós e a quantidade de nós. O primeiro ponto é posicionado em algum lugar aleatório do mapa. A partir do segundo, cada ponto é colocado dentro do raio do anterior. Após plotar todos os pontos, liga-se cada ponto com todos que estão dentro do seu raio, até um certo limite de vizinhos definido no programa. Se um nó tiver a quantidade máxima de vizinhos, então garante-se que o seu antecessor está entre os seus vizinhos. Dessa forma, temos sempre uma topologia aleatória e um grafo conectado mas não completo.

Nossa simulação funciona baseada em rodadas ou turnos, isto é, assim como no protocolo RIP, supomos que o intervalo de tempo entre os envios de tabela é grande o suficiente para que as tabelas de todos os vizinhos chegue e possam ser processadas todas de uma vez. Para simular o comportamento paralelo da troca de tabelas na rede usamos a seguinte idéia: Temos em uma matriz as informações do custo e caminho de cada nó para todos os outros, essa informação é fornecida pelo próprio nó de origem. Em uma outra matriz está uma cópia de como essa tabela estava a uma rodada atrás, que representa a tabela que os roteadores enviaram para seus vizinhos na última rodada e que está no buffer deles para ser processada. Nesse momento, todos os roteadores processam seus buffer e se houver atualização em suas tabelas, eles atualizam a tabela global e notificam seus vizinhos de que eles devem consultar a tabela-cópia na próxima rodada, isso é como se o roteador tivesse colocado sua tabela no buffer de cada um de seus vizinhos.

\section{Dados obtidos}

Os dados coletados foram obtidos enquanto se variava os parâmetros de altura, largura e raio. Durante as experimentações vimos que estes valores ajudavam a alterar o número de arestas que eram geradas aleatoriamente, e somente esse número influenciou os nossos testes, assim, o raio, a largura e a altura não serão discriminados nos dados abaixo, e sim o número de arestas.

Foram realizados várias simulações no programa. Primeiro, foi simulado um número fixo de vértices e arestas, mostrando que o número de trocas de tabelas pouco varia com isso. Depois, foi se variando o número dessas variáveis, verificando seu impacto no número de trocas de tabelas. Abaixo segue uma tabela com os dados obtidos.

\begin{table}[h!]
 \centering
  \begin{tabular}{|c|c|c|}
	\hline Número de vértices & Número de arestas & Número de trocas de tabelas\\
	\hline 20 & 190 & 1235\\
	\hline 20 & 190 & 1349\\
	\hline 20 & 190 & 1349\\
	\hline 20 & 190 & 1387\\
	\hline 20 & 190 & 1425\\
	\hline 19 & 171 & 1044\\
	\hline 18 & 153 & 1139\\
	\hline 17 & 136 & 944\\
	\hline 16 & 120 & 750\\
	\hline 15 & 105 & 686\\
	\hline 15 & 97 & 734\\
	\hline 10 & 24 & 167\\
	\hline 10 & 31 & 161\\
	\hline 10 & 32 & 182\\
	\hline 10 & 36 & 168\\
	\hline 10 & 38 & 197\\
	\hline 10 & 45 & 288\\
	\hline
  \end{tabular}
 \caption{Dados obtidos nas simulações}
\end{table}  

\section{Análise dos dados}

O número de trocas de tabelas que terão no programa depende de quantos nós tem e do número de arestas entre eles. Raio, altura e largura são somente para definir a proximidade dos nós e influenciam no número de arestas que serão então geradas, indiretamente influenciando no número de trocas de tabelas feitas.

\includegraphics[width=400pt,height=300pt]{grafico1.png}
% grafico1.png: 0x0 pixel, 0dpi, 0.00x0.00 cm, bb=

\includegraphics[width=400pt,height=300pt]{grafico2.png}
% grafico2.png: 0x0 pixel, 0dpi, 0.00x0.00 cm, bb=

A partir da análise dos gráficos acima, podemos perceber que a quantidade de trocas de tabela depende linearmente da quantidade de vértices e também depende linearmente da quantidade de arestas. Então, a fórmula do número de trocas de tabelas é da forma x * numVertices + y * numArestas = numTrocas, onde x e y são constantes quaisquer.

É importante observar que a quantidade de arestas só está fazendo com que a quantidade de trocas seja maior, porque estamos considerando que cada roteador terá uma quantidade limitada de vizinhos. Nesse caso, mais arestas significa necessariamente uma rede maior. Porque se o tamanho da rede fosse fixo e a quantidade de arestas fosse aumentando, teríamos um cenário fora do real, já que os roteadores não tem infinitas portas. Como tivemos o cuidado de garantir que não geraríamos um grafo totalmente conectado, quanto mais arestas maior a rede. Podemos então concluir, em última instância, que a quantidade de troca de tabelas depende do tamanho da rede, qualquer variável que afetar o tamanho da rede estará afetando indiretamente a quantidade de troca de tabelas, o que não invalida a fórmula apresentada acima.

\end{document}
